學習資源

https://labuladong.online/algo/data-structure-basic/tree-map-basic/

學習記錄

今天是學習的第 26 天，主要學習了二叉搜索樹的應用：

二叉搜索樹的優勢

二叉搜索樹（BST）的特點是「左小右大」：

對於每一個節點，其左子樹的每個節點的值都要小於這個節點的值，右子樹的每個節點都要大於這個節點的值。

下面的這棵樹就是一棵 BST：

我們可以利用這個左小右大的特性，快速在 BST 中找到某個節點，這就是 BST 的優勢。

在二叉樹中搜索指定節點：

// 在二叉樹中搜索指定節點：
let targetNode = null;

function traverse(root, targetVal) {
    console.log(root);
    if (root === null) {
        return;
    }
    if (root.val === targetVal) {
        // 找到目標節點
        targetNode = root;
    }
    if (targetNode !== null) {
        // 已經找到目標，結束遍歷
        return;
    }

    // 二叉樹遍歷框架
    traverse(root.left, targetVal);
    traverse(root.right, targetVal);
}

// 建立一棵 BST
//        7
//      /   \
//     4     9
//    / \     \
//   1   5    10

var root = new TreeNode(7);

root.left = new TreeNode(4);
root.right = new TreeNode(9);

root.left.left = new TreeNode(1);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(10);

traverse(root, 10);
// 需要遍歷 11 次才找到目標節點 10
// TreeNode {val: 7, left: TreeNode, right: TreeNode}
// TreeNode {val: 4, left: TreeNode, right: TreeNode}
// TreeNode {val: 1, left: TreeNode, right: TreeNode}
// TreeNode null
// TreeNode null
// TreeNode {val: 5, left: TreeNode, right: TreeNode}
// TreeNode null
// TreeNode null
// TreeNode {val: 9, left: TreeNode, right: TreeNode}
// TreeNode null
// TreeNode {val: 10, left: TreeNode, right: TreeNode}

利用 BST 的特性搜索指定節點：

// 利用 BST 的特性搜索指定元素
let targetNode = null;

function traverse(root, targetVal) {
    console.log(root);
    if (root === null) {
        return;
    }
    if (root.val === targetVal) {
        targetNode = root;
    }
    if (targetNode !== null) {
        // 已經找到目標，不需要繼續遍歷了
        return;
    }
    // 根據 targetVal 和當前節點的大小
    // 可以判斷應該去左子樹還是右子樹進行搜索
    if (root.val < targetVal) {
        traverse(root.right, targetVal);
    } else {
        traverse(root.left, targetVal);
    }
}

// 建立一棵 BST
//        7
//      /   \
//     4     9
//    / \     \
//   1   5    10

var root = new TreeNode(7);

root.left = new TreeNode(4);
root.right = new TreeNode(9);

root.left.left = new TreeNode(1);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(10);

traverse(root, 10);
// 只需要遍歷 3 次就能找到目標節點 10
// TreeNode {val: 7, left: TreeNode, right: TreeNode}
// TreeNode {val: 9, left: null, right: TreeNode}
// TreeNode {val: 10, left: null, right: null}

利用 BST 左小右大的特性，理想的時間複雜度是樹的高度 O(log n)，而普通的二叉樹遍歷則需要 O(n) 的時間複雜度。

學習總結

• 二叉搜索樹（BST）的特點是「左小右大」
• 可以利用這個左小右大的特性，快速在 BST 中找到某個節點